package offer.day16;

public class No26isSubStruct {
    /*
     * 面试题26：树的子结构
     * 题目：输入两颗二叉树A和B，判断B是不是A的子结构。
     * 二叉树节点定义：
     * struct BinaryTreeNode{
     * 	double m_dbValue;
     * 	BinaryTreeNode m_pLeft;
     * 	BinaryTreeNode m_pRight
     * }
     *
     * 第一个链表记为A  第二个链表记为B，  方便说明
     * 思路：第一步：首先判断在A中是否有和B的根节点一样的值，递归方式遍历二叉树，若根节点不是，看左节点、右节点
     * 第二步：根据第一步找到的节点，判断其子树是否和B的一样，否则，返回到第一步判断其他节点是否有相等的
     *
     * */

    public static void main(String[] args) {

        No26isSubStruct s = new No26isSubStruct();

        BinaryTreeNode root1 = new BinaryTreeNode(8);
        BinaryTreeNode one = new BinaryTreeNode(8);
        BinaryTreeNode two = new BinaryTreeNode(7);
        BinaryTreeNode three = new BinaryTreeNode(9);
        BinaryTreeNode four = new BinaryTreeNode(2);
        BinaryTreeNode five = new BinaryTreeNode(4);
        BinaryTreeNode six = new BinaryTreeNode(7);

        root1.left = one;
        root1.right = two;
        one.left = three;
        one.right = four;
        two.left = null;
        two.right = null;
        three.left = null;
        three.right = null;
        four.left = five;
        four.right = six;
        five.left = null;
        five.right = null;
        six.left = null;
        six.right = null;

        BinaryTreeNode root2 = new BinaryTreeNode(8);
        BinaryTreeNode first = new BinaryTreeNode(9);
        BinaryTreeNode second = new BinaryTreeNode(2);

        root2.left = first;
        root2.right = second;
        first.left = null;
        first.right = null;
        second.left = null;
        second.right = null;

        if (s.isSubStruct(root1, root2)) {
            System.out.println("第二个二叉树是第一个二叉树的子结构！");
        } else {
            System.out.println("第二个二叉树不是第一个二叉树的子结构！！！！");
        }

    }

    public boolean isSubStruct(BinaryTreeNode root1, BinaryTreeNode root2) {
        if (root1 == null || root2==null) return false;
        return hasSubTree(root1, root2) || hasSubTree(root1.right, root2) || hasSubTree(root1.left, root2);
    }

    public boolean hasSubTree(BinaryTreeNode root1, BinaryTreeNode root2) {
        if (root2 == null) {
            return true;
        }
        if (root1 == null || root1.val!=root2.val) {
            return false;
        }
        return hasSubTree(root1.right, root2.right) && hasSubTree(root1.left, root2.left);
    }

}
